/*
 * Copyright (c) 2019 Wormpex.com. All Rights Reserved.
 */

package com.sk.leetcode.arithmetic;

/**
 * <p>
 * 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
 * <p>
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
 * <p>
 * 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [2,4,1], k = 2
 * 输出: 2
 * 解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
 * 示例 2:
 * <p>
 * 输入: [3,2,6,5,0,3], k = 2
 * 输出: 7
 * 解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
 *      随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv
 * <p>
 * <p>
 * 1，思路。找到最大解。合并
 * 1.1 可以创建链表-方便合并
 * 1.2
 *
 * @author ke.su date: 2019-09-12 Time: 上午10:59
 */
public class Test188 {
    public static void main(String[] args) {
        Test188 test188 = new Test188();
        int[] prices0 = {3, 2, 6, 5, 4, 3, 8, 7, 9, 2, 1};//263879-2609-09
        int[] prices1 = {3, 2, 6, 5, 0, 3, 8, 3, 9, 2, 1};//260839-0839-09
        int[] prices2 = {3, 3, 5, 0, 0, 3, 1, 4};//350314-3504-04
        int[] prices3 = {3, 5, 5, 7, 0, 3, 1, 4};//350314-3504-04
        //394639393939293939   不影响，想多了好像

        //System.out.println(test188.maxProfit(3, prices0));
        //System.out.println(test188.maxProfit(5, prices1));
        //System.out.println(test188.maxProfit(2, prices2));
        System.out.println(test188.maxProfit(4, prices3));

    }

    public int maxProfit(int k, int[] prices) {
        if (prices.length < 2 || k < 1) {
            return 0;
        }

        int length = 0;
        boolean b = prices[0] < prices[1];
        int st = 0, ed = 0;
        if (b) {
            st = prices[0];
        }

        Node start = null;
        Node current = null;

        //循环取出最大切分
        for (int i = 1; i < prices.length; i++) {
            boolean b0 = prices[i - 1] < prices[i];

            if (b) {
                //遇到拐点
                if (!b0) {
                    ed = prices[i - 1];
                    //创建节点
                    length++;
                    Node node = new Node(st, ed);
                    if (current == null) {
                        start = node;
                        current = node;
                    } else {
                        current.next = node;
                        current = node;
                    }
                    st = prices[i];
                    b = false;
                }
            } else {
                if (b0) {
                    b = true;
                    st = prices[i - 1];
                }
            }
        }

        //最后一个拐点处于上升期
        if (b) {
            //创建节点
            length++;
            Node node = new Node(st, prices[prices.length - 1]);
            if (current == null) {
                start = node;
            } else {
                current.next = node;
            }
        }

        //合并
        for (int i = length; k < i; i--) {
            int max = start.ed - start.st + start.next.ed - start.next.st;

            int count0 = start.ed - start.st;
            int count1 = start.next.ed - start.next.st;
            int count2 = start.next.ed - start.st;
            int count = Math.max(count0, Math.max(count1, count2));

            merge(start, start, max - count);
        }

        return sum(start);
    }


    private void merge(Node current, Node maxNode, int maxCou) {
        if (current.next == null) {
            //找到最小合并损方案合并
            Node node = maxNode.next;

            int count0 = maxNode.ed - maxNode.st;
            int count1 = node.ed - node.st;
            int count2 = node.ed - maxNode.st;
            int st = maxNode.st, ed = node.ed;
            if (count0 < count1) {
                maxNode.st = node.st;
                maxNode.ed = node.ed;
            }
            if (count2 > count0) {
                maxNode.ed = ed;
            }
            if (count2 > count1) {
                maxNode.st = st;
            }

            maxNode.next = node.next;
            return;
        }
        //获取最小合并损失
        int max = current.ed - current.st + current.next.ed - current.next.st;

        int count0 = current.ed - current.st;
        int count1 = current.next.ed - current.next.st;
        int count2 = current.next.ed - current.st;

        int count = Math.max(count0, Math.max(count1, count2));
        int cha = max - count;

        if (cha < maxCou) {
            merge(current.next, current, cha);
        } else {
            merge(current.next, maxNode, maxCou);
        }
    }

    private int sum(Node node) {
        if (node == null) {
            return 0;
        }
        return node.ed - node.st + sum(node.next);
    }
}

class Node {
    int st;
    int ed;
    Node next;

    Node(int st, int ed) {
        this.st = st;
        this.ed = ed;
    }
}
